package sword.T56;

/**
 * @Author: 18362
 * @Create: 2022-04-10 1:00:43 星期日
 */
class Solution {
    /**
     * 题解：位运算
     *  结论：
     *      1. 如果一组数字只有1个是不重复的，其他都是重复的，比如[6,6,3,5,5]，那么它们全部异或的结果就是那个不重复的数字
     *      2. 如果一组数字中有两个不重复的数字，其他都是重复的，那么它们全部异或的结果，等同于那两个不重复的数字的异或结果
     *      3. 用一个数字mask和一组数字分别做&运算，就可以根据&运算结果的不同，将这一组数字分成若干组，组的个数与mask二进制中1的个数有关
     *          比如6的二进制是0110，有两个1，就可以将整个数组划分为2^2=4组
     *      4. 两个数字做异或，结果反应的是这两个数字各个位的不同情况，不同位的个数就是结果二进制中1的个数。如果必须将这两个数字分到不同组，那么
     *          可以利用这两个数字的异或结果result来做mask，或者取result中的一个1就可以将他们区分开来
     *  思路：
     *      既然只有两个不同的数字，就可以将整个数组分成两组做异或，必须要确保这两个不同的数字要在不同组，因此要拿这两个异或的结果中的一个1作为mask即可
     *  实现：
     *      1. 将整个数组做异或，得到的结果就是那两个不同的数字做异或的结果，记为result
     *      2. 要将整个数组分为两组，且保证这两个不同的数字能分到不同组，只需要从result中取出一个位上的1作为mask即可。这里取result中最低位的1作为mask
     *      3. 利用mask将整个数组分成两组，每组分别做异或，得到的结果就是这两个不同的数字
     */
    public int[] singleNumbers(int[] nums) {
        int result = 0;
        for (int i=0; i<nums.length; ++i)
            result ^= nums[i];
        int m = 1;
        while ((m & result) == 0) {
            m <<= 1;
        }
        int mask = result & m;
        int a = 0, b = 0;
        for (int i=0; i<nums.length; ++i) {
            if ((mask & nums[i]) == 0)
                a ^= nums[i];
            else
                b ^= nums[i];
        }
        return new int[] {a, b};
    }
}
